#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 1001

// 结点定义
typedef struct Node
{
    int value;
    struct Node *next;
} Node;

// 哈希表定义
typedef struct HashTable
{
    Node *table[MAX_SIZE];
} HashTable;

// 初始化哈希表
void initializeHashTable(HashTable *hashTable)
{
    for (int i = 0; i < MAX_SIZE; ++i)
    {
        hashTable->table[i] = NULL;
    }
}

// 插入操作，时间复杂度 O(1)
void insert(HashTable *hashTable, int element)
{
    int index = element % MAX_SIZE;

    // 创建新结点
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->value = element;
    newNode->next = hashTable->table[index];

    // 更新哈希表
    hashTable->table[index] = newNode;
}

// 删除操作，时间复杂度 O(1)
void remove(HashTable *hashTable, int element)
{
    int index = element % MAX_SIZE;

    Node *current = hashTable->table[index];
    Node *prev = NULL;

    // 在链表中找到要删除的结点
    while (current != NULL && current->value != element)
    {
        prev = current;
        current = current->next;
    }

    // 如果找到，删除结点
    if (current != NULL)
    {
        if (prev == NULL)
        {
            // 要删除的结点是链表的头结点
            hashTable->table[index] = current->next;
        }
        else
        {
            prev->next = current->next;
        }

        free(current);
    }
}

// 按序号查找操作，时间复杂度 O(1)
int getByIndex(HashTable *hashTable, int index)
{
    if (index < 1 || index > MAX_SIZE)
    {
        return -1; // 索引超出范围，返回-1表示未找到
    }

    int count = 0;
    for (int i = 0; i < MAX_SIZE; ++i)
    {
        Node *current = hashTable->table[i];

        while (current != NULL)
        {
            ++count;

            if (count == index)
            {
                return current->value; // 返回对应索引位置的元素
            }

            current = current->next;
        }
    }

    return -1; // 未找到
}

// 主程序
int main()
{
    HashTable myHashTable;
    initializeHashTable(&myHashTable);

    int a, b;
    do
    {
        printf("请输入操作方式和操作数（按逗号隔开）\n");
        printf("操作方式为-1表示退出:\n");
        scanf("%d,%d", &a, &b);
        if (a == 1)
        {
            insert(&myHashTable, b);
        }
        else if (a == 2)
        {
            remove(&myHashTable, b);
        }
        else if (a == 3)
        {
            int result = getByIndex(&myHashTable, b);
            printf("Element at index %d: %d\n", b, result);
        }
    } while (a != -1);

    return 0;
}
